package com.example.demo.LinearTable.LFU;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
 * put(key, value) - 如果键不存在，请插入。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
 * 可以在O(1)时间内完成以上两项操作。
 */
public class LFU {

    /**
     * 为了可以在O(1)时间完成get(key)操作，很容易想到使用HashMap
     */
    private HashMap<Integer, Node> cache;

    /**
     * 算法要求使用次数相等时，要删去最近最少使用的键，
     * 因此可以在相同频率的K中维护一个双向链表，最近使用的对象放在头部，删去时直接删在尾部。
     */
    private HashMap<Integer, LinkedList<Node>> fredMap;

    /**
     * 缓存的容量
     */
    private int capacity;

    /**
     * 记录被使用的次数
     */
    private int minFred;

    public LFU(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
        fredMap = new HashMap<>();
        minFred = 0;
    }

    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        fredIncreaseByCached(node);
        return node.getValue();
    }

    /**
     * node已缓存的情况
     */
    private void fredIncreaseByCached(Node node) {
        int fred = node.getFred();
        // 从原频率链表中删除
        LinkedList<Node> fredList = fredMap.get(fred);
        fredList.remove(node);
        // 如果该node代表全局最低频率，记得更新最小频率值
        if (node.getFred() == minFred && fredList.isEmpty()) {
            minFred++;
        }
        // 插入新的频率链表（头插），记得将fred+1
        fredList = fredMap.get(fred + 1);
        if (fredList == null || fredList.size() == 0) {
            fredList = new LinkedList<>();
            fredMap.put(fred + 1, fredList);
        }
        fredList.addFirst(node);
        node.fredInc();
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        // 情况1：缓存已存在
        Node node = cache.get(key);
        if (node != null) {
            node.setValue(value);
            fredIncreaseByCached(node);
            return;
        }

        // 情况2：缓存未存在
        node = new Node(key, value);
        // 2.1 缓存已满，需要先删除freq最小的list中最不常用的节点（尾结点）
        if (cache.size() == capacity) {
            LinkedList<Node> fredList = fredMap.get(minFred);
            Node last = fredList.removeLast();
            cache.remove(last.getKey(), last);
        }
        // 2.2 缓存未满，直接插入，注意此时该node对应fred为0（首次插入）；头插法
        cache.put(key, node);
        LinkedList<Node> fredList = fredMap.computeIfAbsent(0, k -> new LinkedList<>());
        fredList.addFirst(node);
        minFred = 0;
    }

    public static void main(String[] args) {
        LFU cache = new LFU(3);
        cache.put(3, 1);
        cache.put(2, 1);
        System.out.println(cache.cache.keySet());
        cache.put(2, 2);
        System.out.println(cache.cache.keySet());

        cache.put(4, 4);
        System.out.println(cache.cache.keySet());

        int res1 = cache.get(2);
        System.out.println(res1);

        int res2 = cache.get(3);
        System.out.println(res2);

        int res3 = cache.get(2);
        System.out.println(res3);

        int res4 = cache.get(1);
        System.out.println(res4);

        cache.put(5, 5);

        int res5 = cache.get(1);
        System.out.println(res5);

        int res6 = cache.get(2);
        System.out.println(res6);

        int res7 = cache.get(3);
        System.out.println(res7);

        int res8 = cache.get(4);
        System.out.println(res8);

        int res9 = cache.get(5);
        System.out.println(res9);
    }
}

class Node {
    private int key;
    private int value;
    private int fred = 0;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public int getValue() {
        return value;
    }

    public int getFred() {
        return fred;
    }

    public void fredInc() {
        fred++;
    }
}

class GateTest {
    public static void main(String[] args) {
        LFU cache = new LFU(2 /* capacity (缓存容量) */);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);       // 返回 1
        cache.put(3, 3);    // 去除 key 2
        cache.get(2);       // 返回 -1 (未找到key 2)
        cache.get(3);       // 返回 3
        cache.put(4, 4);    // 去除 key 1
        cache.get(1);       // 返回 -1 (未找到 key 1)
        cache.get(3);       // 返回 3
        cache.get(4);       // 返回 4
    }

}

